В черный ящик
кладут листки с числами. На каждом листке записано ровно одно целое число.
Время от времени некоторые листки исчезают из ящика.
После каждого
события (добавления или исчезновения листка) необходимо вывести число, которое
встречается наибольшее количество раз среди всех оставшихся в ящике. Если таких
чисел несколько, следует вывести наименьшее из них.
Вход. Первая строка содержит количество событий n (1 ≤ n ≤ 2 * 105). Каждая из следующих n строк описывает одно событие:
·
+ x – в ящик положен листок с
числом x (1 ≤ x ≤ 106);
·
- x – из ящика исчез листок с
числом x (гарантируется, что в ящике есть хотя бы один такой листок).
Выход. Выведите ровно n строк – по одной на каждое событие. В
каждой строке должно быть одно число – ответ на задачу.
Если после какого-либо
события ящик пуст, выведите 0.
|
Пример
входа |
Пример
выхода |
|
3 + 1 - 1 + 2 |
1 0 2 |
РЕШЕНИЕ
дерево отрезков
Рассмотрим массив a0, a1, …, a1000000, изначально заполненный нулями. При
выполнении событий:
·
+ x выполняем операцию a[x]++;
·
- x выполняем операцию
a[x]--;
Таким образом,
число, которое встречается наибольшее количество раз среди всех листков,
соответствует максимальному значению в массиве на отрезке [0; 106]. Если таких
чисел несколько, следует выбрать наименьшее из них.
Для эффективного
моделирования операций с массивом можно использовать дерево отрезков,
поддерживающее нахождение максимума. Каждая вершина vvv этого дерева будет
содержать пару (x,
freq[x]), где freq[x] – текущее значение a[x].
Объявим дерево
отрезков.
struct node
{
int x, freq;
};
vector<node> SegTree;
Функция max сравнивает два элемента типа node. Она возвращает вершину с большей
частотой. Если
частоты обеих вершин совпадают, возвращается вершина с меньшим значением x.
struct node max(node a, node b)
{
if (a.freq > b.freq) return a;
if ((a.freq == b.freq) && (a.x < b.x)) return a;
return b;
}
Функция BuildTree строит дерево
отрезков.
void BuildTree(int v, int lpos, int rpos)
{
if (lpos == rpos)
{
SegTree[v].x = lpos;
SegTree[v].freq = 0;
}
else
{
int mid = (lpos + rpos) / 2;
BuildTree(2 * v, lpos, mid);
BuildTree(2 * v + 1, mid + 1, rpos);
SegTree[v] = max(SegTree[2 * v], SegTree[2 * v + 1]);
}
}
Функция Add выполняет операцию прибавления a[pos] += val.
void Add(int v, int lpos, int rpos, int pos, int val)
{
if (lpos == rpos)
SegTree[v].freq += val;
else
{
int mid = (lpos + rpos) / 2;
if (pos <= mid)
Add(2 * v, lpos, mid, pos, val);
else
Add(2 * v + 1, mid + 1, rpos, pos, val);
SegTree[v] = max(SegTree[2 * v], SegTree[2 * v + 1]);
}
}
Основная часть программы. Читаем количество событий n.
cin >> n;
Строим дерево отрезков.
SegTree.resize(4 * MAX);
BuildTree(1, 0, MAX - 1);
Последовательно обрабатываем запросы.
while (n--)
{
cin >> c >> x;
if (c == '+') Add(1, 0, MAX - 1, x, 1);
else Add(1, 0, MAX - 1, x, -1);
cout << SegTree[1].x << endl;
}